/*
 * Populacao.cpp
 *
 *  Created on: 18/10/2012
 *      Author: vagner
 */

#include "Populacao.h"
#include "Individuo.h"
#include <vector>
#include <cstdlib>
#include <iostream>
#include <unistd.h>
#include <sys/time.h>

namespace computacaoNatural {

Populacao::Populacao() {
	//Do nothing

}

Populacao::Populacao(int vertices, int medianas, Grafo* g,
		ParametrosManager* pm) {

	if (vertices > 0 && medianas > 0) {
		this->numVertices = vertices;
		this->numMedianas = medianas;
	}

	if (g != 0 && pm != 0) {
		this->pGrafo = g;
		this->pParametros = pm;
	}
	for (int i = 0; i < pm->TAM_POP; i++) {
		Individuo* individuoAux = new Individuo(i, numMedianas, numVertices);
		//individuoAux->show();
		Individuos.push_back(*individuoAux);
		delete individuoAux;
		//usleep((unsigned)900000);
	}
}

void Populacao::avaliaFitness() {

	std::vector<Individuo>::iterator itIndividuos;

	for (itIndividuos = Individuos.begin(); itIndividuos != Individuos.end();
			itIndividuos++) {
		itIndividuos->calculaFitness(this->pGrafo);
	}

}

inline bool Populacao::findInVector(const std::vector<int>& Lista,
		int item) const {

	return (std::find(Lista.begin(), Lista.end(), item) != Lista.end());
}

void Populacao::sorteia(int n, int p, std::vector<int>& valoresSorteados) {

	timeval time;
	gettimeofday(&time,NULL);
	std::srand(time.tv_sec*time.tv_usec);
	int num_random;

	while (int(valoresSorteados.size()) < p) {

		if(n == 0 || n < 0){
			valoresSorteados.push_back(0);
		}else{
			num_random = std::rand() % n;
			//std::cout << "Numero gerado: " << num_random << std::endl;
			if (!findInVector(valoresSorteados, num_random)) {
				//std::cout << "Numero inserido: " << num_random << std::endl;
				valoresSorteados.push_back(num_random);
			}
		}

	}

}

void Populacao::realizaTorneio(int numParticipantes) {

	std::vector<candidato> partipantesTorneio;
	std::vector<int>::iterator itInt;
	std::vector<candidato>::iterator itCandidatos;

	std::vector<int> idPartipantes;
	//Identificador dos particantes do torneio;
	int idPerdedor;
	candidato candidatoTemp;

	while (this->Individuos.size()
			> pParametros->TAM_POP / pParametros->TAM_TORNEIO) {

		//Sorteia os participantes do torneio
		sorteia((int) Individuos.size(), numParticipantes, idPartipantes);

		//Escolhendo os participantes do torneio
		for (itInt = idPartipantes.begin(); itInt != idPartipantes.end();
				itInt++) {
			candidatoTemp.idCandidato = (*itInt);
			candidatoTemp.chave = Individuos.at((*itInt)).getFitness();
			partipantesTorneio.push_back(candidatoTemp);
		}

		//Definindo o vencedor
		ordenaVerticesCandidatos(partipantesTorneio);

		//Apagando os perderdores
		for (size_t i = 1; i < partipantesTorneio.size(); i++) {

			idPerdedor = partipantesTorneio.at(i).idCandidato;
			//Apagando o perdedor
			this->Individuos.erase(Individuos.begin() + idPerdedor);
		}

		//Apagando dos torneior
		idPartipantes.clear();
		partipantesTorneio.clear();
	}
}

void Populacao::selecaoNatural() {
	realizaTorneio(this->pParametros->TAM_TORNEIO);
}

inline double Populacao::funcaoProb() {
	std::srand((unsigned) time(0));
	int num_random;
	float prob;

	num_random = std::rand();

	prob = (double) num_random / (double) RAND_MAX;

	return prob;
}

void Populacao::aplicaOperadoresGeneticos() {


	int numIndividuos = (int) Individuos.size();
	int numExeOpGeneticos = numIndividuos * pParametros->MAX_OP_GENETICOS;
	std::vector<int> participantes;
	float prob;
	int idPrimIndividuo;
	int idSegIndividuo;

	for (int index = 0; index < numExeOpGeneticos; index++) {

		numIndividuos = (int) Individuos.size();

		if (numIndividuos > 1) {
			prob = funcaoProb();
			sorteia(numIndividuos, 2, participantes);
			idPrimIndividuo = participantes.at(0);
			idSegIndividuo = participantes.at(1);
			if (Individuos.at(idPrimIndividuo)
					== Individuos.at(idSegIndividuo)) {
				/*
				 * Se os individuos são iguais, um deles é excluido e o outro
				 * é mantido na população
				 */
				Individuos.erase(Individuos.begin() + idSegIndividuo);

			} else if (0 <= prob && prob <= pParametros->pMUT) {
				mutacao(Individuos.at(idPrimIndividuo));
				mutacao(Individuos.at(idSegIndividuo));
			} else if (prob <= pParametros->pCROSS) {
				crossover(Individuos.at(idPrimIndividuo),
						Individuos.at(idSegIndividuo));
			}
			participantes.clear();
		}else{
			break;
		}

	}
}

void Populacao::mutacao(Individuo& i) {

	int novoAlelo;
	std::vector<int> alelos;
	while (true) {
		sorteia(pGrafo->getNumVertices(), 1, alelos);
		novoAlelo = alelos.at(0);
		if (!i.findAlelo(novoAlelo)) {
			i.alteraAlelo(pParametros->ALELO_MUTAVEL, novoAlelo);
			break;
		}
	}
}

void Populacao::crossover(Individuo& i1, Individuo& i2) {

	/*
	 * O crossover consiste em basicamente verificar quais alelos do invididuo 1
	 * não estão no individuo 2. O mesmo processo é feito para o individuo 2.
	 * Depois é escolhido randonicamente um valor entre 1 e c-1, onde c é numero de alelos que
	 * esta em um individuo e não está no outro. A partir primeiro alelo, c alelos serão trocados.
	 */

	//Lista que contem os alelos que estão
	//no individuo 1 e não estao no individuo 2
	std::vector<int> *exchVector_1 = 0;

	//Lista que contem os alelos que estão
	//no individuo 2 e não estao no individuo 1
	std::vector<int> *exchVector_2 = 0;

	//std::cout<< "Crossover dos individuos: "<<std::endl;
	//i1.show();
	//i2.show();

	int tamExchVector_1;
	int tamExchVector_2;
	int qtdeAlelosTrocados;
	std::vector<int> alelosTrocados;

	exchVector_1 = i1.diferenca(i2);
	exchVector_2 = i2.diferenca(i1);
	tamExchVector_1 = (int) exchVector_1->size();
	tamExchVector_2 = (int) exchVector_2->size();

	if((tamExchVector_1) == 0 || tamExchVector_2 == 0) {
		/*
		 * Suponha dos individuos com os fenotios a,b e b,a
		 * Eles serao considerados diferentes. Contudo o exchange vector será vazio;
		 * Logo não será possível realizar troca tendo em vista que esta troca pode colocar
		 * dos alelo identicos. Para evitar esta situção os dois individuos serao reproduzidos
		 */
		return;

	}

	//Alterando os alelos do Individuo 1
	sorteia((tamExchVector_1) - 1, 1, alelosTrocados);

	qtdeAlelosTrocados = alelosTrocados.at(0) + 1;
	for (int i = 0; i < qtdeAlelosTrocados; i++) {
		i1.alteraAlelo(i, exchVector_2->at(i));
	}
	alelosTrocados.clear();

	//Alterando os alelos do Individuo 1
	sorteia((tamExchVector_2 - 1), 1, alelosTrocados);
	qtdeAlelosTrocados = alelosTrocados.at(0) + 1;
	for (int i = 0; i < qtdeAlelosTrocados; i++) {
		i2.alteraAlelo(i, exchVector_1->at(i));
	}
	exchVector_1->clear();
	exchVector_2->clear();
	delete exchVector_1;
	delete exchVector_2;
}

void Populacao::calculaMelhorPiorFitness(double* melhor, int* indexMelhor, double* pior, int* indexPior) {

	int tamPopulacao = (int) this->Individuos.size();

	if ((tamPopulacao & 1) > 0) { //Se o tamanho for impar
		this->Individuos.push_back(Individuos.at(tamPopulacao - 1));
		tamPopulacao++;
	}
	if (Individuos.at(0).getFitness() <= Individuos.at(1).getFitness()) {
		*melhor = Individuos.at(0).getFitness();
		*indexMelhor = 0;
		*pior = Individuos.at(1).getFitness();
		*indexPior = 1;
	} else {
		*melhor = Individuos.at(1).getFitness();
		*indexMelhor = 1;
		*pior = Individuos.at(0).getFitness();
		*indexPior = 0;
	}

	for (int i = 3; i < tamPopulacao; i += 2) {

		if (Individuos.at(i - 1).getFitness()
				<= Individuos.at(1).getFitness()) {

			if (Individuos.at(i - 1).getFitness() < *melhor) {
				*melhor = Individuos.at(i - 1).getFitness();
				*indexMelhor = (i-1);
			}

			if (Individuos.at(i).getFitness() > *pior) {
				*pior = Individuos.at(i).getFitness();
				*indexPior = i;
			}
		} else {

			if (Individuos.at(i).getFitness() < *melhor) {
				*melhor = Individuos.at(i).getFitness();
				*indexMelhor = (i);
			}

			if (Individuos.at(i - 1).getFitness() > *pior) {
				*pior = Individuos.at(i - 1).getFitness();
				*indexPior = i-1;
			}
		}

	}
}

double Populacao::calculaFitnessMedia() {

	std::vector<Individuo>::iterator itIndividuos;
	long double fitnessMedia = 0.0;
	int numIndividuos = (int) Individuos.size();

	for (itIndividuos = Individuos.begin(); itIndividuos != Individuos.end();
			itIndividuos++) {
		fitnessMedia += itIndividuos->getFitness();
	}
	fitnessMedia = fitnessMedia / numIndividuos;
	return fitnessMedia;
}

void Populacao::show(void) const {

	size_t i;

	for (i = 0; i < Individuos.size(); i++) {
		Individuos.at(i).show();
	}
}

void Populacao::showIndividuo(int idIndividuo){
	this->Individuos.at(idIndividuo).show();
}

Populacao::~Populacao() {
	//Do nothing
}

}/* namespace computacaoNatural */
